Status: accepted (2026-11-19, maintainer). Elements of are nimbers by default; Conway polynomials are the secondary representation and the default for every other ; the cryptographersβ polynomials (AES, GHASH, β¦) are alternatives for cryptanalysis and interoperability.
Code:
julia/FiniteFieldArithmetic.jl/src/nimber.jl(and its notenimber.md). Backlog: J1a, J1b, J7, V6.
Context
A field has many concrete representations, one per choice of basis; the usual one is a polynomial basis modulo an irreducible polynomial of degree . The maintainer asked for the choice that gives the most structure, especially across several fields, rather than a polynomial picked by cryptographers for cheap reduction. The projectβs purpose (general theory, cryptanalysis, learners built on finite fields) favours structure and bulk arithmetic over interoperability.
Options considered
- Conway polynomials , for every : the lexicographically least monic primitive polynomial of degree over compatible with for all , i.e. . Then the embeddings , , commute. Categorically: finite fields of characteristic 2 have embeddings when (one per Galois automorphism); Conway polynomials choose one coherently, a functor from the divisibility poset into fields whose colimit is a concrete . Since is primitive, discrete logarithms are compatible as well. Costs: βleastβ is a convention (the compatibility is the structure); the tables (LΓΌbeck) end at some degree, beyond which pseudo-Conway polynomials (compatible, not minimal) must be computed; they are dense, so reduction is slower than with a trinomial.
- Nimbers (Conway, On Numbers and Games, ch. 6), for : the integers below
with XOR and nim-multiplication form , and these fields are
nested as sets of integers. The embedding keeps the bit pattern; no polynomial is chosen at all
(each level is the ArtinβSchreier extension by a root of of the one below). The
union is the quadratic closure of , and levels 3β7 are exactly the byte-sized
fields of 8β128 bits, the maintainerβs priority. Lean: the
CombinatorialGames project defines
Nimber(on our toolchain v4.36.0); mathlib v4.36.0 has neither nimbers nor Conway polynomials. Cost: no hardware instruction like carry-less multiplication helps; the large levels must be benchmarked against polynomial bases. - Standard low-weight polynomials (AES , GHASH ): fast reduction and interoperability with existing software; no structure across fields.
Decision
Nimbers for , Conway polynomials (pseudo-Conway beyond the tables) for other and for , standard polynomials as alternatives. A change of representation is an -linear map (an bit matrix), cheap in bulk.
Consequences
- Subfield arithmetic is free in the nimber representation: GF(16) values are GF(256) values,
so mixed-level arithmetic is promotion, and one set of GF(256) tables serves every level up to
it (measured:
nimber.md). - Conversions between representations must be explicit (no implicit isomorphism); elements of different representations compare unequal.
- Fields that are not of the form (e.g. ) wait for the Conway representation (J1b).